The present invention relates to viterbi decoding for decoding convolutional codes, and more specifically, to a technique for reducing power consumption in path storage means.
Viterbi decoding is used in the maximum likelihood decoding of convolutional codes. Because of its high ability to correct errors, viterbi decoding is used in decoders of a transmission system such as satellite communications and satellite broadcasting, which tend to cause transmission errors.
In recent years, as demodulating circuits have become faster and had larger packing densities, viterbi decoders, which are smaller in circuit size, lower in power consumption and operative at higher speed have been presented (Refer to Japanese Patent Publication No. 2996615 for example).
In addition, in viterbi decoding, there has been a conventional technique for reducing power consumption in the path memory. FIG. 16 shows a conventional viterbi decoder with a structure to reduce power consumption in the path memory (disclosed in Japanese Laid-Open Patent Application No. 8-46524). To simplify the explanation, this drawing indicates the case where the encoding rate is xc2xd and the constraint length (the number of shift registers contained in a convolutional encoder+1) K=3.
In FIG. 16, an ACS (Add Compare Select) circuit 700 generates path select signals from reception codes entered therein. A majority circuit 701 outputs xe2x80x9c0xe2x80x9d when there are more xe2x80x9c0xe2x80x9ds than xe2x80x9c1xe2x80x9ds in the 4-bit path select signals outputted from the ACS circuit 700, and outputs xe2x80x9c1xe2x80x9d when there are more xe2x80x9c1xe2x80x9ds than xe2x80x9c0xe2x80x9ds. A first conversion unit 702 includes means 702a to 702d each for generating an XOR of an output of the ACS circuit 700 and the corresponding output of the majority circuit 701. Receiving xe2x80x9c1xe2x80x9d as the output of the majority circuit 701, the means 702a to 702d reverse the path select signals received from the ACS circuit 700. The outputs of the majority circuit 701 are also stored in a storage delay unit 703.
The storage delay unit 703 delays the outputs of the majority circuit 701 by the length of the delay in decoding, and outputs them at the same timing as the corresponding path select signals are outputted from the path memory 704. A second conversion unit 705 includes means 705a to 705d each for generating an XOR of an output of the path memory 704 and the corresponding output of the storage delay unit 703. When the output of the storage delay unit 703 is xe2x80x9c1xe2x80x9d, the means 705a to 705d reverse the path select signals outputted from the path memory 704 so as to return the path select signals to their original states.
Through these operations, the path select signals stored in the path memory 704 are supposed to have more logical value xe2x80x9c0xe2x80x9ds than xe2x80x9c1xe2x80x9ds. Consequently, the signal transition in the path memory 704 occurs less frequent so as to reduce power consumption, thereby achieving a viterbi decoder operative with lower power consumption.
However, the above-mentioned conventional structure requires a majority circuit, a storage delay unit and conversion units as add-on circuits for an intrinsic viterbi decoder. This undesirably increases the circuit size, thereby boosting the power consumption in the large add-on circuits when the constraint length becomes large or when a delay in decoding is extended in order to improve the ability to correct errors.
Moreover, a majority circuit usually operates slower as the number of target bits increases, so that the above-mentioned conventional structure is not suitable for a viterbi decoder, which requires high-speed operations.
The present invention has an object of reducing power consumption in the path storage means for storing path select signals in viterbi decoding in a different manner from conventional methods.
To be more specific, the present invention relates to a viterbi decoder and a viterbi decoding method for performing decoding by using path storage means for storing path select signals, performing the steps of: partially tracing back path select signals outputted from ACS means between a first time point and a second time point, thereby finding surviving paths reaching each node at the first time point; detecting a non-passing node through which said surviving paths do not pass, of nodes at the second time point; converting a path select signal corresponding to said non-passing node at the second time point in such a manner as to decrease a probability of occurrence of a signal transition in said path storage means; and storing path select signals corresponding to said nodes at the second time point to said path storage means.
According to the present invention, a path select signal which is never referred to in a trace back for decoding and which corresponds to a non-passing node is so converted as to decrease the probability of occurrence of a signal transition in the path storage means. The decrease in the probability of occurrence of a signal transition in the path storage means results in a reduction in power consumption.
In the viterbi decoder and viterbi decoding method, it is preferable that said path select signal corresponding to said non-passing node is converted into a predetermined fixed value which is one of signal values of said path select signal. Consequently, the path storage means statistically contains the logical value corresponding to the predetermined fixed value more than the other logical value, thereby making the dispersion of logical value uneven. As a result, the probability of occurrence of a signal transition in the path storage means becomes lower than in the case where no conversion is performed, thereby restricting power consumption in the path storage means.
In the viterbi decoder and viterbi decoding method, it is preferable that said path select signal corresponding to said non-passing node is converted into a same value as a value already stored in a storage region in said path storage means where said path select signal to be converted is supposed to be written. Consequently, the probability of occurrence of a signal transition in the path storage means becomes lower than in the case where no conversion is performed, thereby restricting power consumption in the path storage means.
The present invention also relates to a viterbi decoder which has path storage means for storing path select signals and which performs decoding by using said path storage means, said viterbi decoder comprising: a path temporary storage unit for storing path select signals outputted from ACS means over a certain period of time and then outputting said path select signals; a partial trace back unit for tracing back surviving paths reaching each node at time t+p by using path select signals between time t and time t+pxe2x88x921 where p is a natural number which are stored in said path temporary storage unit and path select signals at time t+p outputted from said ACS means so as to detect a non-passing node through which said surviving paths do not pass; and a conversion unit for inputting path select signals at time t outputted from said path temporary storage unit, and receiving signals from said partial trace back unit so as to convert a path select signal corresponding to said non-passing node out of said path select signals at time t into a predetermined fixed value which is one of signal values of said path select signal, said path storage means storing path select signals at time t outputted from said conversion unit.
Alternatively, the present invention relates to a viterbi decoder which has path storage means f or storing path select signals and which perform decoding by using said path storage means, said viterbi decoder comprising: a path temporary storage unit for storing path select signals outputted from ACS means over a certain period of time and then outputting said path select signals; a partial trace back unit for tracing back surviving paths reaching each node at time t+p by using path select signals between time t and time t+pxe2x88x921 where p is a natural number which are stored in said path temporary storage unit and path select signals at time t+p outputted from said ACS means so as to detect a non-passing node through which said surviving paths do not pass; readout means for reading out storage contents in a storage region in said path storage means where path select signals at time t are supposed to be written; and a conversion unit for inputting said path select signals at time t outputted from said path temporary storage unit and said storage contents outputted from said readout means and receiving signals from said partial trace back unit so as to convert a path select signal corresponding to said non-passing node out of said path select signals at time t into a same value as a value which is contained in said storage contents and stored in a storage region where said path select signal to be converted is supposed to be written, said path storage means storing path select signals at time t outputted from said conversion unit.
It is preferable that said partial trace back unit finds a function g (t, j) concerning each node j at time t, and determines that node j is a non-passing node when g (t, j)=0, where g (t, i) is a function for calculating g (r, i)=xcexa3{g (r+1, n (i))xc3x97f (r, n (i))} from r=t+pxe2x88x921 until r=t in sequence by using g (t+p, k)=1 as an initial value where k is an any node number, where
n (i): transition target nodes at time r+1 of a node i at time r;
f (r, n (i)): a function which indicates whether or not surviving paths reaching nodes n (i) at time r+1 pass through node i at time r, and which becomes xe2x80x9c1xe2x80x9d when said surviving paths pass through said nodes i, xe2x80x9c0xe2x80x9d otherwise;
xcexa3{ }: an OR of all said nodes n (i); and
xc3x97: AND.
This indicates that the partial trace back unit is realized by a small-sized circuit, based on the nature of calculation. In other words, according to the present invention, detection of a non-passing node is executed by repetitive calculations of simple ANDs and ORs, making it possible to construct the partial trace back unit by a small-sized calculator.
It is further preferable that said partial trace back unit comprises a plurality of storage means for storing each value of g (r, i) at time r, and performs calculation of said function g (t, j) by pipeline processing. Consequently, the calculation of g (t, j) can be executed by being divided into a plurality of cycles. As a result, the amount of calculation per cycle can be lessened, thereby realizing a high-speed detection of a non-passing node.
The present invention further relates to a viterbi decoder and a viterbi decoding method for per-forming decoding by using path storage means, performing the steps of: applying predetermined conversion to path select signals outputted from ACS means; storing converted path select signals in said path storage means; applying conversion reverse to said predetermined conversion to path select signals outputted from said path storage means; and performing decoding by using reversely-converted path select signals, said predetermined conversion being so conducted that, out of combinations of path select signals representing surviving paths in a predetermined portion in a trellis diagram, a first combination with a relatively high frequency of occurrence contains a predetermined fixed value which is one of signal values of said path select signals more than a second combination with a relatively low frequency of occurrence.
According to the present invention, before being stored in the path storage means, the path select signals outputted from the ACS means are so converted that the combination with a relatively high frequency of occurrence has the predetermined fixed value which is one of the signal values of the path select signals more than the combination with a relatively low frequency of occurrence. Consequently, the path storage means statistically contains the logical value corresponding to the predetermined fixed value more than the other value, thereby making the dispersion of logical value uneven. As a result, the probability of occurrence of a signal transition in the path storage means becomes lower than in the case where no conversion is performed, thereby restricting power consumption in the path storage means.
It is preferable that said predetermined conversion is performed by using a combination of path select signals with a relatively few number of merges of surviving paths as the first combination, and a combination of path select signals with a relatively large number of merges of surviving paths as the second combination.